All telecommunication is subject to the problem of how to make sure that the received information is sent by an authorized sender and not by somebody who is trying to masquerade as the sender. The problem is evident in cellular telecommunication systems, where the air interface presents an excellent platform for eavesdropping and replacing the contents of a transmission by using higher transmission levels, even from a distance. A basic solution to this problem is authentication of the communicating parties. An authentication process aims to discover and check the identity of both of the communicating parties, so that each party receives information about the identity of the other party, and can trust the identity to a sufficient degree. Authentication is typically performed in a specific procedure at the beginning of the connection. However, this leaves room for unauthorized manipulation, insertion, and deletion of subsequent messages. Thus, there is a need for separate authentication of each transmitted message. The latter task can be done by appending a message authentication code (MAC) to the message at the transmitting end, and checking the MAC value at the receiving end.
A MAC is typically a relatively short string of bits, which depends in some specified way on the message it protects and on a secret key known both by the sender and by the recipient of the message. The secret key is generated and agreed typically in connection with the authentication procedure in the beginning of the connection. In some cases the algorithm that is used to calculate the MAC based on the secret key and the message is also secret but this is not usually the case.
The process of authentication of single messages is often called integrity protection. To protect the integrity of signaling, the transmitting party computes a MAC value based on the message to be sent and the secret key using the specified algorithm, and sends the message with the MAC value. The receiving party recomputes a MAC value based on the message and the secret key according to the specified algorithm, and compares the received MAC and the calculated MAC. If the two MAC values match, the recipient can trust that the message is intact and sent by the supposed party. One may note in passing, that integrity protection does not usually include protection of confidentiality of the transmitted messages.
Integrity protection schemes are not completely perfect. A third party can try to manipulate and succeed in manipulating a message transmitted between a first and a second party. There are two main alternative methods for forging a MAC value for a modified or a new messages, namely by obtaining the secret key first, and by trying directly without the secret key.
The secret key can be obtained by a third party basically in two ways:                by computing all possible keys until a key is found, which matches with data of observed message-MAC pairs, or by otherwise breaking the algorithm for producing MAC values; or        by directly capturing a stored or transmitted secret key.        
The original communicating parties can prevent a third party from obtaining the secret key by using an algorithm that is cryptographically strong and which uses a long enough secret key to prevent exhaustive search of all keys, and using other security means for transmission and storage of secret keys.
A third party can try to disrupt messaging between the two parties without a secret key basically by guessing the correct MAC value, or by replaying of some earlier message transmitted between the two parties, for which message the correct MAC is known from the original transmission.
Correct guessing of the MAC value can be prevented by using long MAC values. The MAC value should be long enough to reduce the probability of guessing right to a sufficiently low level compared to the benefit gained by one successful forgery. For example, using a 32 bit MAC value reduces the probability of a correct guess to 1/4 294 967 296, which is small enough for most applications.
Obtaining a correct MAC value using the replay attack i.e. by replaying an earlier message can be prevented by introducing a varying parameter to the calculation of the MAC values. For example, a time stamp value, a sequence number, or a random number can be used as a further input to the MAC algorithm in addition to the secret integrity key and the message. The present invention is associated with this basic method. In the following, the prior art methods are described in more detail.
When using a time stamp value, each communicating party needs to have an access to a reliable clock in order to be able to calculate the MAC in the same way. The problem with this approach is the need of the reliable clock. The clocks of both parties must be very accurate and be very accurately in time. However, this condition is unacceptable in cellular telecommunication systems: both parties, i.e. the mobile station (MS) and the network do not have access to a clock, that is reliable enough.
When using sequence numbers, each party has to keep track of those sequence numbers that have already been used and are not acceptable any more. The easiest way to implement this is to store the highest sequence number used in MAC calculations so far. This approach has the drawback, that between connections each party must maintain state information which is at least to some level synchronized. That is, they need to store the highest sequence number used so far. This requires the use of a large database at the network side.
A further approach is to include a random number in each message, which the other side must use in MAC calculation when for the next time sending a message, for which MAC authentication is required. This approach has the same drawback as the previous one, i.e. between connections each party must maintain state information, which requires the use of a large database at the network side.
U.S. Pat. No. 5,475,763 by Kaufman et al. (1995) describes a signature system, such as an El Gamal or DSS system, involving the use of long term secret number and a per-message secret number generates the per message secret number without the use of a random number generator or non-volatile storage. The per-message secret number is generated by applying a one-way hash function to a combination of the long term secret number and the message itself.